package com.maltys.monotonic.stack;

import java.lang.reflect.Array;
import java.util.*;

/**
 * @author maltys
 * @link <a href="https://leetcode.cn/problems/next-greater-element-i/">下一个更大的数I</a>
 */
public class NextGreaterElementI {
    public static void main(String[] args) {
        NextGreaterElementI elementI = new NextGreaterElementI();
        int[] ints = elementI.nextGreaterElement(new int[]{4, 1, 2}, new int[]{1, 3, 4, 2});
        System.out.println(Arrays.toString(ints));
    }

    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<>();
        LinkedList<Integer> que = new LinkedList<>();
        que.add(nums2[0]);
        for (int i = 0; i < nums2.length; i++) {
            while (!que.isEmpty() && nums2[i] > que.peekLast()) {
                map.put(que.removeLast(), nums2[i]);
            }
            que.addLast(nums2[i]);
        }
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            res[i] = map.getOrDefault(nums1[i], -1);
        }
        return res;
    }
}
